浅谈分块

分块，就是一种优雅的暴力。它可以将 $O(n^2)$ 的暴力变成 $O(n \sqrt{n})$

一、如何实现分块

如图：

实现：

int n, T; scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", A + i); // 数组
t = sqrt(n); // 块长
for (int i = 1; i <= t; i++) {
    L[i] = (i - 1) * t + 1;
    R[i] = i * t;
} // L 表示块的左边界, R表示块的右边界
if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
for (int i = 1; i <= t; i++) {
    for (int j = L[i]; j <= R[i]; j++) {
        pos[j] = i; // pos[j]表示第j个数所处的块的位置
        sum[i] += A[j]; // sum[i]表示第i个块的和
    }
}

二、如何实现加法

如果让你在 $[l, r]$ 之间的每个数都加上 $k$ ，对块进行如图操作（这里 $l = 3, r = 13$）：

实现：

void upd(int l, int r, LL val) {
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
	else {
		for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
		for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
		for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
	}
}

三、如何实现查询

如果让你在 $[l, r]$ 之间的每个数都加上 $k$ ，对块进行如图操作（这里 $l = 6, r = 17$）：

实现：

LL query(int l, int r) {
	LL ret = 0ll;
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
	else {
		for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
		for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
		for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
	}
	return ret;
}

总体实现（例题 P3372）：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
LL A[N], sum[N], tag[N];
int pos[N], L[N], R[N], t;
void upd(int l, int r, LL val) {
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
	else {
		for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
		for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
		for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
	}
}
LL query(int l, int r) {
	LL ret = 0ll;
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
	else {
		for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
		for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
		for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
	}
	return ret;
}
int main() {
	int n, T; scanf("%d%d", &n, &T);
	for (int i = 1; i <= n; i++) scanf("%lld", A + i);
	t = sqrt(n);
	for (int i = 1; i <= t; i++) {
		L[i] = (i - 1) * t + 1;
		R[i] = i * t;
	}
	if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
	for (int i = 1; i <= t; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			sum[i] += A[j];
		}
	}
	LL k;
	for (int op, l, r; T--; ) {
		scanf("%d%d%d", &op, &l, &r);
		if (op == 1) scanf("%lld", &k), upd(l, r, k);
		else printf("%lld\n", query(l, r));
	}
	return 0;
}

四、如何插入元素

如果让你在位置 $x$ 插入一个元素，你可以在每一个块内弄一个双端队列，固定块长，如图（以 $x = 6$ 为例）：

将 $8$ 从第二个块的末尾弹出，进入第三个块的前端，$12$ 、$16$ 同理。这里显然不能直接手写 $deque$ ，所以可以用 $STL$ 中的 $deque$ 来实现插入元素和单点查询，复杂度 $O(n \sqrt{n})$（插入 $O(\sqrt{n})$ ，从 $deque$ 中暴力查询 $O(\sqrt{n})$）。

如果想要手写 $deque$，可以开一个 $2$ 倍块长的数组，如下表进行操作：

开始时：

第 $1$ 次：

第 $2$ 次：

$\cdots$ 第 块长（$=4$）次：

当到头了的时候，我们可以将其暴力放到末尾：

一次暴力的复杂度时 $O(\sqrt{n})$ ，但这需要 $\sqrt{n}$ 次操作后才可以进行该操作，所以均摊到每次操作上就是 $O(1)$ 的。

可以发现，这样做可以将查询的时间复杂度降到 $O(1)$ ，代码实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
const int Block_Start = 801; // Block_Size = Block_Start
int Size, B[N];
struct per {
	int A[Block_Start << 1 | 5], Al = Block_Start, Ar = Block_Start;
	per() {Al = Ar = Block_Start;}
	void insert(int pos, int val) {
		for (int i = Ar - 1; i >= Al + pos - 1; i--) A[i + 1] = A[i];
		A[Al + pos - 1] = val; Ar++;
	}
	void Move_Back() {
		if (Al > Block_Start - Size) return;
		for (int i = Ar - 1; i >= Al; i--) A[Block_Start - Al + i] = A[i];
		int tsz = Ar - Al;
		Al = Block_Start; Ar = Al + tsz;
	}
	int query(int pos) {
		return A[Al + pos - 1];
	}
}p[505];
LL min(LL x, LL y) {return x < y ? x : y;}
LL max(LL x, LL y) {return x > y ? x : y;}
void Roll_To_Next_Block(int Block) {
	while (p[Block].Ar - p[Block].Al > Size) {
		p[Block + 1].A[--p[Block + 1].Al] = p[Block].A[--p[Block].Ar];
		p[Block + 1].Move_Back();
		Block++;
	}
}
void upd(int pos, int val) {
	int Block = (pos - 1) / Size + 1;
	p[Block].insert(pos - (Block - 1) * Size, val);
	Roll_To_Next_Block(Block);
}
int query(int pos) {
	int Block = (pos - 1) / Size + 1;
	return p[Block].query(pos - (Block - 1) * Size);
}
int main() {
    srand((unsigned)time(0));
	int n, T; scanf("%d", &n); T = n;
	for (int i = 1; i <= n; i++) scanf("%d", B + i);
	Size = sqrt(n * 2.5);
	for (int i = 1, Block; i <= n; i++) {
		Block = (i - 1) / Size + 1;
		p[Block].insert(i - (Block - 1) * Size, B[i]);
	}
	int tot = n;
	for (int op, l, r, k; T--; ) {
		scanf("%d%d%d%d", &op, &l, &r, &k);
		if (op == 0) upd(l, r);
		else printf("%d\n", query(r));
	}
	return 0;
}

感谢观看！